package nachos.threads;

import nachos.machine.*;

import java.util.HashSet;
import java.util.Set;
import java.util.Formatter;

/**
 * Base class for schedulers that use some sort of prioritization to
 * schedule threads. Currently subclassed by PriorityScheduler and
 * LotteryScheduler.
 */
public abstract class BasePriorityScheduler extends Scheduler {

    /**
     * The default priority for a new thread.
     */
    public final int priorityDefault;

    /**
     * The minimum priority that a thread can have.
     */
    public final int priorityMinimum;

    /**
     * The maximum priority that a thread can have.
     */
    public final int priorityMaximum;    

    /**
     * Allocate a new priority scheduler with the given default,
     * minimum, and maximum priorities.
     */
    public BasePriorityScheduler(int priorityDefault,
				 int priorityMinimum,
				 int priorityMaximum) {
	this.priorityDefault = priorityDefault;
	this.priorityMinimum = priorityMinimum;
	this.priorityMaximum = priorityMaximum;
    }

    /**
     * Return the priority of the given thread.
     */
    public int getPriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	return getThreadState(thread).getPriority();
    }

    /**
     * Return the effective priority of the given thread, which may be
     * different from the result of getPriority it is the recipient of
     * priority donations.
     */
    public int getEffectivePriority(KThread thread) {
	Lib.assertTrue(Machine.interrupt().disabled());
	return getThreadState(thread).getEffectivePriority();
    }

    /**
     * Set the priority of the given thread to priority, or fail if
     * priority is outside the range of acceptable priorities.
     */
    public void setPriority(KThread thread, int priority) {
	Lib.assertTrue(Machine.interrupt().disabled());
		       
	Lib.assertTrue(priority >= priorityMinimum &&
		       priority <= priorityMaximum);

	getThreadState(thread).setPriority(priority);
    }

    /**
     * Return the scheduling state of the specified thread.
     *
     * @param	thread	the thread whose scheduling state to return.
     * @return	the scheduling state of the specified thread.
     */
    protected ThreadState getThreadState(KThread thread) {
	if (thread.schedulingState == null)
	    thread.schedulingState = newThreadState(thread);

	return (ThreadState) thread.schedulingState;
    }

    /**
     * Subclasses should implement this so that it returns a new
     * ThreadState for the given thread.
     */
    protected abstract ThreadState newThreadState(KThread thread);

    /**
     * Increase the priority of the current thread, if
     * possible. Return boolean indicating whether or not we actually
     * increased the priority.
     */
    public boolean increasePriority() {
	boolean intStatus = Machine.interrupt().disable();
	KThread thread = KThread.currentThread();
	int priority = getPriority(thread);
	boolean canIncrease = priority < priorityMaximum;

	if (canIncrease) {
	    setPriority(thread, priority+1);
	}

	Machine.interrupt().restore(intStatus);
	return canIncrease;
    }

    /**
     * Decrease the priority of the current thread, if
     * possible. Return boolean indicating whether or not we actually
     * decreased the priority.
     */
    public boolean decreasePriority() {
	boolean intStatus = Machine.interrupt().disable();
	KThread thread = KThread.currentThread();
	int priority = getPriority(thread);
	boolean canDecrease = priority > priorityMinimum;
	
	if (canDecrease)
	    setPriority(thread, priority-1);

	Machine.interrupt().restore(intStatus);
	return canDecrease;
    }


    /**
     * Base class for thread queues that release threads based on some
     * kind of priority.
     */
    protected abstract class PriorityQueue<T extends ThreadState> 
	extends ThreadQueue implements Iterable<T>
    {

	/**
	 * Construct a new PriorityQueue. If transferPriority is true,
	 * then threads waiting on the queue will have their priority
	 * transferred to the owner of the queue. It is up to the
	 * implementation to determine the semantics of this transfer.
	 */
	PriorityQueue(boolean transferPriority) {
	    this.transferPriority = transferPriority;
	}
	
	/**
	 * <tt>true</tt> if this queue should transfer priority from waiting
	 * threads to the owning thread.
	 */
	public boolean transferPriority;

	/**
	 * The last thread that was popped off this queue, and is
	 * currently blocking other threads on the queue.
	 */
	protected T owner = null;


	@Override
	public String toString() {
	    Formatter fmt = new Formatter();
	    fmt.format("  %s%n", super.toString());
	    fmt.format("  Owner: %s%n", owner);
	    fmt.format("  Transfer priority: " + transferPriority);
	    int i = 0;
	    for (T ts : this) {
		i++;
		fmt.format("  %4d %s%n", ts);
	    }
	    return fmt.toString();
	}
	public void print() {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    System.out.println(this);
	}

	/**
	 * Sets my owner to the given thread and calls owner(this) on
	 * that thread, in order to add this queue to its list of
	 * owned queues and clear out its wait queue.
	 */
	public void acquire(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    owner = (T)getThreadState(thread);
	    owner.acquire(this);
	}

	/**
	 * Return true if there are no threads on the queue, false
	 * otherwise.
	 */
	public boolean isEmpty() {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    return !iterator().hasNext();
	}

	/**
	 * Add the given thread to the end of the queue.
	 */
	public void waitForAccess(KThread thread) {
	    Lib.assertTrue(Machine.interrupt().disabled());
	    
	    T ts = (T)getThreadState(thread);

	    // If this thread currently owns this queue, then release
	    // the ownership since this thread is moving to the back
	    // of the line.
	    if (owner == ts)
		owner = null;

	    // Add the thread to the end of the queue, notify it that
	    // it is waiting on my queue, and move it up to its proper
	    // position in the heap.
	    addThread(ts);
	    ts.waitForAccess(this);
	}

	public KThread nextThread() {

	    Lib.assertTrue(Machine.interrupt().disabled());

	    // If a thread owns this queue, break that ownership, and
	    // recalculate the owner's effective priority, since it
	    // may have lost some priority donations.
	    if (owner != null) {
		owner.ownedQueues.remove(this);
		owner.calculateEffectivePriority();
		owner = null;
	    }

	    // If there isn't a thread on the queue, just return null.
	    if (isEmpty()) 
		return null;

	    // The next thread on the queue should become my
	    // owner. Pop it, let it acquire me, and return it.
	    owner = pop();
	    owner.acquire(this);
	    return owner.thread;
	}

	/**
	 * Subclasses should implement this so that it removes the
	 * next thread from its internal data structure and returns
	 * it, without changing any of the priorities.
	 */
	public abstract T pop();

	/**
	 * Subclasses should implement this so that it adds the given
	 * thread to whatever internal datastructure is used to hold the
	 * threads.
	 */
	public abstract void addThread(T t);

    }

    /**
     * Base class for the state associated with a thread.
     */
    protected abstract class ThreadState<T extends PriorityQueue> {

	public ThreadState(KThread thread) {
	    this.thread = thread;
	    setPriority(priorityDefault);
	}

	/**
	 * Subclasses should implement this so that it sets the
	 * priority, recalculates the effective priority, and performs
	 * required adjustments to the queue.
	 */
	public abstract void setPriority(int priority);

	/**
	 * Subclasses should implement this so that it recalculates
	 * the effective priority of the thread.
	 */
	public abstract void calculateEffectivePriority();

	/**
	 * Called when <tt>waitForAccess(thread)</tt> (where <tt>thread</tt> is
	 * the associated thread) is invoked on the specified priority queue.
	 * The associated thread is therefore waiting for access to the
	 * resource guarded by <tt>waitQueue</tt>. This method is only called
	 * if the associated thread cannot immediately obtain access.
	 *
	 * @param	waitQueue	the queue that the associated thread is
	 *				now waiting on.
	 *
	 * @see	nachos.threads.ThreadQueue#waitForAccess
	 */
	public void waitForAccess(T waitQueue) {
	    this.waitQueue = waitQueue;
	    if (ownedQueues.remove(waitQueue)) {
		calculateEffectivePriority();
	    }
	}

	public String toString() {
	    return String.format("%20s %4d (%4d)", 
				 thread, getPriority(), getEffectivePriority());
	}

	/**
	 * Return the priority of the associated thread.
	 *
	 * @return	the priority of the associated thread.
	 */
	public int getPriority() {
	    return priority;
	}

	/**
	 * Return the effective priority of the associated thread.
	 *
	 * @return	the effective priority of the associated thread.
	 */
	public int getEffectivePriority() {
	    return effectivePriority;
	}

	/**
	 * Called when the associated thread has acquired access to whatever is
	 * guarded by <tt>waitQueue</tt>. This can occur either as a result of
	 * <tt>acquire(thread)</tt> being invoked on <tt>waitQueue</tt> (where
	 * <tt>thread</tt> is the associated thread), or as a result of
	 * <tt>nextThread()</tt> being invoked on <tt>waitQueue</tt>.
	 *
	 * @see	nachos.threads.ThreadQueue#acquire
	 * @see	nachos.threads.ThreadQueue#nextThread
	 */
	public void acquire(T waitQueue) {

	    Lib.assertTrue(Machine.interrupt().disabled());
	    ownedQueues.add(waitQueue);

	    this.waitQueue = null;
	}

	/** The thread with which this object is associated. */	   
	protected KThread thread;
	/** The priority of the associated thread. */
	protected int priority;

	protected int effectivePriority;

	/** 
	 * The queue that this thread is waiting on, or null if it's
	 * active.
	 */
	public T waitQueue;

	/**
	 * Set of queues that this thread currently owns. We use this
	 * to determine whether there is a higher priority thread that
	 * is being blocked by this thread.
	 */
	public Set<T> ownedQueues = new HashSet<T>();
	
    }


}